package com.lsa.letcode.the61.rotateList;

import com.lsa.letcode.common.ListNode;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 * 
 * 1-2-3-4-5, >> 2 ---> 4-5-1-2-3
 * 1-2-3-4-5, >> 1 ---> 5-1-2-3-4
 * 1-2-3-4-5, >> 0 ---> 1-2-3-4-5 
 */
public class Solution {
    public ListNode rotateRight(ListNode head, int k) {
    	if (head == null || head.next == null || k == 0) {
    		return head;
    	}
    	
    	ListNode fast = head;
    	int len = 0;
    	for (int i = 0; i < k; i++) {
    		len++;
    		fast = fast.next;
    		if (fast == null){
    			break;
    		}
		}
    	
    	if (fast == null) {
    		return rotateRight(head, k % len);
    	}
    	
    	ListNode slow = head;
    	ListNode newTail = null;
    	ListNode oldTail = null;
    	while(fast != null) {
    		newTail = slow;
    		slow = slow.next;
    		oldTail = fast;
    		fast = fast.next;
    	}
    	
    	oldTail.next = head;
    	newTail.next = null;
    	
    	return slow;
    }
}